class ListNode:
    # 创建一个指针结点
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def mergeLists(list1, list2):
    # 创建一个节点作为新链表的起点
    head = ListNode()
    current = head

    # 遍历两个链表
    while list1 and list2:
        if list1.val < list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    # 如果有一个链表已经结束，将另一个链表的剩余部分接到结果链表后面
    if list1:
        current.next = list1
    elif list2:
        current.next = list2

    # 返回新链表的头节点，即节点的下一个节点
    return head.next


def createList(arr):
    if not arr:
        return []
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# 打印合并后的链表
def printList(node):
    if not node:
        print("[]")
        return
    while node:
        list = []
        while node:
            list.append(node.val)
            node = node.next
        print(list)


if __name__ == '__main__':
    l1 = createList([1, 2, 4])
    l2 = createList([1, 3, 4])
    merged_list = mergeLists(l1, l2)
    printList(merged_list)
